class Solution {
    int mem[31];
public:
    int fib(int n) {
        memset(mem,-1,sizeof(mem));
        return dfs(n);
    }
    int dfs(int n)
    {
        if(mem[n]!=-1)
            return mem[n];
            
        if(n==0 || n==1)
        {
            mem[n]=n;
            return n;
        }

        mem[n]=dfs(n-1)+dfs(n-2);
        return mem[n];
    }
};
